//
// Description: 5663. 找出第k大的异或坐标值
// Created by Loading on 2021/1/24.
//

#include <bits/stdc++.h>

using namespace std;

int kthLargestValue(vector<vector<int>> &matrix, int k) {
    vector<vector<int>> vec;
    int m = matrix.size();
    int n = matrix[0].size();
    vector<int> sort_vec;

    for (int i = 0; i < m; ++i) {
        vector<int> v;//新矩阵每一行的数据
        //每一行第一个值
        if (i == 0) {
            v.push_back(matrix[0][0]);
        } else {
            v.push_back(matrix[i][0] ^ vec[i - 1][0]);//当前行第一个值 XOR 上一行第一个值
        }
        for (int j = 1; j < n; ++j) {
            if (i == 0) {//第一行
                v.push_back(matrix[i][j] ^ v[j - 1]);//当前值 XOR 左侧值
            } else {
                //当前值 XOR 上侧值 XOR 左侧值 XOR 左上侧值
                v.push_back(matrix[i][j] ^ vec[i - 1][j] ^ v[j - 1] ^ vec[i - 1][j - 1]);
            }
        }

        vec.push_back(v);
    }

    //转为一维矩阵查找备用
    for (const auto &v : vec) {
        for (const auto &x : v) {
            sort_vec.push_back(x);
        }
    }
    for (auto x : sort_vec) {
        cout << x << " ";
    }
    cout << endl;

    //寻找第k大的数，其实是指排序后第 m * n - k - 1 下标处的数，题目不严谨
    nth_element(sort_vec.begin(), sort_vec.begin() + m * n - k, sort_vec.end());

    return sort_vec[m * n - k];
}

int main() {
    vector<vector<int>> vec = {{10, 9, 5},
                               {2,  0, 4},
                               {1,  0, 9},
                               {3,  4, 8}};
    int k = 10;

    cout << kthLargestValue(vec, k) << endl;
}

